Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?

摘要

This paper introduces quantum ``multiple-Merlin''-Arthur proof systems inwhich Arthur receives multiple quantum proofs that are unentangled with eachother. Although classical multi-proof systems are obviously equivalent toclassical single-proof systems (i.e., usual Merlin-Arthur proof systems), it isunclear whether or not quantum multi-proof systems collapse to quantumsingle-proof systems (i.e., usual quantum Merlin-Arthur proof systems). Thispaper presents a necessary and sufficient condition under which the number ofquantum proofs is reducible to two. It is also proved that, in the case ofperfect soundness, using multiple quantum proofs does not increase the power ofquantum Merlin-Arthur proof systems.